|
A Turing machine is a hypothetical device with an infinite memory capacity, first conceived by Alan Turing in 1936. The machine manipulates symbols on a potentially infinite strip of tape according to a table of rules, and can be adapted to simulate the logic of any computer algorithm. While none of the following models have been shown to have more power than the single-tape, one-way infinite, multi-symbol Turing-machine model, their authors defined and used them to investigate questions and solve problems more easily than they could have if they had stayed with Turing's ''a''-machine model. == Machines equivalent to the Turing machine model == Turing equivalence Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power. They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (The Church-Turing thesis ''hypothesizes'' this to be true: that anything that can be “computed” can be computed by some Turing machine.) The sequential-machine models All of the following are called "sequential machine models" to distinguish them from "parallel machine models".〔Peter van Emde Boas, ''Machine Models and Simulations''; Jan van Leeuwen, ed. ''Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity'', p. 3-66, The MIT Press/Elsevier, 1990. ISBN 0-262-72014-0 (volume A). QA76.H279 1990.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Turing machine equivalents」の詳細全文を読む スポンサード リンク
|